Many network applications send and receive data messages using an encryption scheme. As used herein, the term “encryption scheme” refers to a communication protocol that incorporates an encryption algorithm, which enciphers and deciphers data. The original data processed by an encryption algorithm are referred to as “plain text” and the encrypted data produced by the encryption algorithm are referred to as “cipher text.” Encryption schemes optionally include additional functionality, such as authentication of encrypted messages.
Encryption schemes are broader than an encryption algorithm alone because an encryption algorithm using a single encryption key in isolation cannot generate a large number of messages in a cryptographically secure manner. Note that this limitation does not imply that the encryption algorithm is inadequate for use in sending highly secured communications. For example, even the Rijndael algorithm used in the Advanced Encryption Standard (AES), which is believed to be cryptographically secure for sensitive communications, cannot be used in isolation to guarantee secured communications indefinitely.
For an illustrative example of how even a strong encryption algorithm can be used in an insecure manner, imagine a scenario where a sender, Alice, wishes to send single letters of the English alphabet A-Z to a receiver, Bob. Alice and Bob share a 128-bit key encryption key that is kept secret so that an attacker Eve does not know what the key is. Alice uses the AES algorithm with the secret key to encrypt plain text data in 128-bit blocks. In this example, Alice encrypts a series of plain text letters “B”, “O”, and “B” to send to Bob. Note that since AES is a binary block cipher, Alice converts each letter to a binary representation, such as ASCII or Unicode, and then “pads” the individual letters with zeros or other appropriate padding data so that each plain text letter is represented by 128 bits of data to match the block size of the AES algorithm in this example. The following are contrived examples of cipher text messages sent to Bob, represented using hexadecimal numbers: B→0xf3ea8951017b1797aaa01a3eldb054aa, O→0x1737f10771fe999518c936eaf32b98cb, and B→0xf3ea8951017b1797aaa01a3eldb054aa.
While the lengthy hexadecimal numbers for the cipher text listed above may appear to provide a great deal of security, note that the letter “B” is encrypted to the same cipher text value twice in the above example. Simplifying the above example yields B→B′, O→O′, B→B′ where B′ and O′ are the cipher text values corresponding to the “B” and “O” plain text. Each of the other letters in the alphabet map to a single cipher text representation in the same manner.
If Alice sends Bob a non-trivial number of encrypted characters using the example described above, then the data include numerous repetitions of the same plain text letters and resulting cipher text messages that provide a great deal of information about the plain text to the attacker Eve. While the cipher text appears to be difficult to decrypt, the scenario described above is actually equivalent to a simple text-substitution cipher, such as cryptogram puzzles commonly published in newspapers, which can be solved by hand using frequency analysis and other known techniques. The weakness is not directly in the AES encryption algorithm, which Eve has not compromised, but in the fact that the encryption algorithm is deterministic, which is to say that the AES algorithm using one key always produces the exact same output given a single input. The deterministic nature of the encryption algorithm enables Bob to decrypt messages using the same key in a reliable manner, but requires a more sophisticated encryption scheme that goes beyond the encryption algorithm to prevent an attacker from extracting information from the cipher text.
Numerous encryption schemes that are known to the art prevent the types of attacks described above. While numerous variations exist, each of the schemes ensures that a given cryptographic key only encrypts any unique set of data a single time during the life of the key. Of course, Alice likely wants to send Bob the same piece of plain text, such as letters in the alphabet, numerous times without having to change the encryption key. The encryption schemes ensure that repeated messages including the same plain text are encrypted into cipher text messages that appear to be unpredictable and non-repeating to an attacker during the life of the cryptographic key.
The counter mode (CTR) encryption scheme is a commonly used encryption scheme that enables Alice to send the same plain text repeatedly while also ensuring that the encryption key does not encrypt a single set of data multiple times. In the CTR scheme, the encryption key does not encrypt the plain text directly, but instead encrypts a binary representation of a numeric counter. The encrypted counter is then used to transform the plain text, typically using a binary exclusive-or (XOR) operation, to generate the final cipher text for an encrypted message. The counter value is modified after each encryption operation, often by incrementing the counter value by 1. In a digital computer, the counter value is usually represented as an unsigned integer using a predetermined number of bits, such as 128 bits in one configuration, and the increment process uses modulo arithmetic so that if the counter value exceeds the maximum 128-bit number, the counter “wraps around” to zero and continues incrementing. The numeric range of the counter is sufficiently large to enable the encryption key to generate a large amount of encrypted data without encrypting the same counter value more than one time. If at some point the counter is exhausted, then the encryption scheme includes a method for both Alice and Bob to generate a new shared encryption key and the CTR mode begins again.
In the CTR encryption scheme, both Alice and Bob use a common counter value to encrypt and decrypt, respectively, each message. In existing systems, Alice typically sends Bob an initial counter value and Alice and Bob both increment the counter value in a predetermined manner. Note that Alice can send Bob the initial counter value in an unencrypted manner since Eve cannot decrypt the cipher text with only the initial counter value. In the CTR scheme, Alice can send Bob messages including any data without repetition. Thus, Alice can send repetitive plain text messages, such as A, A, A, and Eve sees a different cipher text corresponding to each plain text message without regard to the content of the plain text.
In addition to obscuring the plain text from Eve, the CTR scheme prevents Eve from performing a playback attack in which Eve records an earlier encrypted message and simply sends the message to Bob again, even if Eve does not know the plain text of the message. The playback attack fails because Bob modifies his counter after the first copy of the encrypted message arrives. When Eve sends the copy of the encrypted message, Bob has already updated the counter value so that the expected counter value for a new message does not correspond to the counter value used to generate the copied message, and Bob can identify that the copied message is invalid.
CTR mode encryption schemes are widely used in modern communication networks. For example, in an unrealistically ideal network, Bob receives every message that Alice sends without corruption and Bob receives multiple messages in the same order that Alice sent the multiple messages. In a more realistic high-speed data network, such as an Ethernet local area network (LAN), a high percentage of messages sent by Alice reach Bob, and higher-level communication protocols, such as the transmission control protocol (TCP), ensure that Alice retransmits the occasional lost message and that Bob receives the messages in the correct order. In the networks describe above, Alice can send Bob the initial counter value one time and both Alice and Bob update the counter value to maintain synchronization for a large number of encrypted messages.
CTR encryption schemes have drawbacks in situations where maintaining synchronization of the counter between the sender and the receiver is difficult. Unlike the network examples presented above, many data networks tend to lose a large number of messages and operate at comparatively low transmission data rates. Two examples of such networks are the controller area network (CAN) bus networks used in many automotive and industrial applications and low-power wireless sensor networks. These networks operate in environmentally hostile conditions where the rate of message loss is much higher than in the Ethernet networks described above. Additionally, the data rates in the CAN bus and wireless sensor networks are typically much slower than in high-speed data networks. For example, the CAN bus standard typically operates with a transfer rate of 250 kilobits of data per second, while Ethernet networks operate in a range of tens of megabits to 100 gigabits and beyond in various configurations.
When a message sent from Alice to Bob is lost, Bob does not update his copy of the counter when Alice sends a subsequent message to Bob. Thus, Alice and Bob lose counter synchronization when a message is lost. Additionally, since the unreliable networks operate at lower speeds, retransmitting messages to guarantee delivery or sending large amounts of redundant information is often impractical. In the past, lower reliability networks, such as CAN bus and wireless sensor networks, have simply sent messages in plain text instead of implementing strong encryption schemes. With the proliferation of network connectivity for different systems and threats from online attackers, however, encryption is becoming more important for use in network devices that have traditionally communicated using plain text. Consequently, improvements to CTR mode encryption schemes that provide improved encrypted communication in low reliability networks would be beneficial.